线性表
- 顺序表
- 链接表
顺序表
在顺序表中，元素存储在一块大存储区中，元素间的逻辑顺序关系通过实际存储位置直接反映，元素存储位置可以基于下标算出。
在 Python 的官方实现中，list 是一种采用分离式技术实现的动态顺序表。
list 操作的复杂度分析：
- len() O(1) 操作
- 特殊情况：表的尾端插入和删除是 O(1)
- 一般位置（包括首端）的插入、删除、切片、替换、extend 都是 O(n)
- clear() O(1)
- reverse() O(n)
- sort() O(nlogn)
链接表
不要求逻辑上相邻的两个元素物理上也相邻，通过“链”建立数据元素间的逻辑关系
插入、删除不需要移动数据元素，只需要修改“链”
注意：节点类的定义和链表类的定义一定要分清
链表操作的复杂度：
- 创建空表 O(1)
- 删除表 O(1)
- 判断空表 O(1)
- 首端加入 O(1)
- 尾端加入 O(n): 需要遍历找出前面的一个节点（最后一个节点）
- 定位加入 O(n): 同理
- 首端删除 O(1)
- 尾端删除 O(n)
- 定位删除 O(n)
表的遍历
Python 语言为内部汇集（collection）类型提供的遍历机制是迭代器，关键字是 yield，标准使用方式是放在 for 语句头部
多重链表
链表中的节点可能同时隶属于多个链
- 多重链表中节点的指针域会有多个
- 但包含两个指针域的链表并不一定是多重链表，比如双向链表
树和图这种相对复杂的数据结构可以用多重链表方式实现
链表的变形和操作
单链表的简单变形
单链表：每个节点只有一个指针域
可以在类定义中引入表尾指针 self._rear
类设计的内在一致性：要采用同样的原则
复杂度分析：
- 首端插入和删除 O(1)
- 尾端插入 O(1)
- 尾端删除 O(n) 由于节点只有指向下一个节点的指针域，表尾指针的前一个节点仍然需要遍历才能得出
循环单链表
只有表尾指针，表尾节点的下一个节点是链表的首节点
- 首端插入和删除 O(1)
- 尾端插入 O(1)
- 尾端删除 O(n) 表尾指针的前一个节点仍然需要遍历才能得出
双链表（双向链接表）
表头指针和表尾指针
双向链接节点
复杂度分析：
- 首端插入和删除 O(1) 表头指针
- 尾端插入和删除 O(1) 表尾指针（能得到表尾指针的前一个节点）
链表操作
反转（reverse）
顺序表反转：用首尾两个下标，通过逐对交换元素位置并把下标向中间位置移动，直到两个下标碰头，操作完成
链接表反转：
- 双链表可以像顺序表那样操作，因为有表头表尾两个指针
- 对于单链表，在表的首端删除和插入是 O(1) 复杂度
注意：当循环条件不容易确定时，可以用 while Ture:，再用 if...break 语句跳出循环
排序（sort）
[ ] 插入排序